An arithmetic read-once formula (ROF) is a formula (circuit of fan-out 1)over $+,\times$ where each variable labels at most one leaf. Every multilinearpolynomial can be expressed as the sum of ROFs. In this work, we prove, forcertain multilinear polynomials, a tight lower bound on the number of summandsin such an expression.
展开▼
机译：一次算术只读公式（ROF）是一个超过$ + \ times $的公式（扇出1电路），其中每个变量最多标记一个叶子。每个多线性多项式都可以表示为ROF的总和。在这项工作中，我们证明了在确定多项式多项式的情况下，此类表达式中summands数量的严格下限。
展开▼
